⟸ pàgina anterior ⟸
Exercici 1 (Tasca 4).
(context-free languages, pumping lemma)

Només incontextual o en realitat regular?

Més endavant en el curs veurem que no existeix cap algorisme que sempre acabi i respongui la pregunta “Donada una gramàtica incontextual, genera un llenguatge regular?”.

Per a cadascuna de les gramàtiques incontextuals de sota, trobeu quin és el llenguatge generat i demostreu si és un llenguatge regular o no.

  1. \left\{\begin{array}{ccl} S &\to& AB \mid CD \\ A &\to& 0A0 \mid 0 \\ B &\to& 1B1 \mid \lambda \\ C &\to& 0C0 \mid \lambda \\ D &\to& 1D1 \mid \lambda \end{array}\right.
  2. \left\{\begin{array}{ccl} S &\to& aA \mid bB \mid \lambda \\ A &\to& Sa \mid Sb \\ B &\to& Sb \end{array}\right.
  3. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& 0A0 \mid 1 \\ B &\to& 1B1 \mid 0 \end{array}\right.
  4. \left\{\begin{array}{ccl} S &\to& 0S0 \mid 0S1 \mid \lambda \end{array}\right.
  5. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& 0A0 \mid 0A1 \mid \lambda \\ B &\to& 0B \mid 1B \mid \lambda \end{array}\right.
  6. \left\{\begin{array}{ccl} S &\to& A \mid B \\ A &\to& 0S0 \mid 1S1 \mid \lambda \\ B &\to& 0S1 \mid 1S0 \mid \lambda \end{array}\right.
  7. \left\{\begin{array}{ccl} S &\to& A \mid B \\ A &\to& 0A0 \mid 1A1 \mid \lambda \\ B &\to& 0B1 \mid 1B0 \mid \lambda \end{array}\right.
  8. \left\{\begin{array}{ccl} S &\to& aSa \mid bSb \mid X \\ X &\to& aXb \mid bXa \mid a \mid b \mid \lambda \end{array}\right.
  9. \left\{\begin{array}{ccl} S &\to& WXW' \\ X &\to& aX \mid bX \mid \lambda \\ W &\to& aW \mid bW \mid \lambda \\ W' &\to& W'a \mid W'b \mid \lambda \end{array}\right.